Data Structure of Berkeley(1)

List

Store a list of ints as an array. Disadvantages of array.

1. Insert item of beginning or middle take time proportional to length of array
2. Arrats have a fixed length.

LINKED LISTS(a recursive data type)

Made up of "nodes". Each node has *an item *a reference to the next node

public class ListNode{
    int item;
    ListNode next;
}
//Let’s make some ListNodes.
ListNode l1 = new ListNode(), l2 = new ListNode(), l3 =           new ListNode();
l1.item = 7;
l2.item = 0;
l3.item = 6;
/*-------------         -------------         -------------
   |     ----- |         |     ----- |         |     ----- |
   | item| 7 | |         | item| 0 | |         | item| 6 | |
   l1-->|     ----- |    l2-->|     ----- |    l3-->|     ----- |
   |     ----- |         |     ----- |         |     ----- |
   | next| ? | |         | next| ? | |         | next| ? | |
   |     ----- |         |     ----- |         |     ----- |
   -------------         -------------         ------------Now let’s link them together.*/
     l1.next = l2;
     l2.next = l3;
     /*What about the last node?  We need a reference that doesn’t reference anything.In Java, this is called "null".*/
     l3.next = null;
       /*       -------------         -------------         -------------
   |     ----- |         |     ----- |         |     ----- |
   | item| 7 | |         | item| 0 | |         | item| 6 | |
   l1-->|     ----- |    l2-->|     ----- |    l3-->|     ----- |
   |     ----- |         |     ----- |         |     ----- |
   | next| .-+-+-------->| next| .-+-+-------->| next| X | |
   |     ----- |         |     ----- |         |     ----- |
   -------------         -------------         -------------    */

Node Operations

to simplify programming ,

public ListNode(int item , ListNode next)
{
    this.item=item;
    this.next=next;   
}